package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author tzp
 * @since 2020/9/15
 */
public class LC139 implements DynamicProblem {
    public boolean wordBreak(String s, List<String> wordDict) {
        Map<Integer, Boolean> cache = new HashMap<>();
        return re(s, wordDict, 0, cache);
    }

    public boolean re(String s, List<String> wordDict, int start, Map<Integer, Boolean> cache) {
        if (cache.containsKey(start)) {
            return cache.get(start);
        }
        boolean result = false;
        if (start < s.length()) {
            for (int i = 0; i < wordDict.size(); i++) {
                String word = wordDict.get(i);
                if (s.startsWith(word, start)) {
                    boolean re = re(s, wordDict, start + word.length(), cache);
                    if (re) {
                        result = true;
                        break;
                    }
                }
            }
        } else if (start == s.length()) {
            result = true;
        }
        cache.put(start, result);
        return result;
    }

    public static void main(String[] args) {

        {
//            String s = "applepenapple";
//            List<String> wordDict = Arrays.asList("apple", "pen");
//            System.out.println(new LC139().wordBreak(s, wordDict));
        }
        {
            String s = "catsandog";
            List<String> wordDict = Arrays.asList("cats", "dog", "sand", "and", "cat");
            System.out.println(new LC139().wordBreak(s, wordDict));
        }


    }
}
